<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>快速排序之单边循环法</title>
  </head>
  <body>
    <script type="text/javascript">
      function quickSort(arr, startIndex, endIndex) {
        // 递归结束条件: startIndex 大于或等于 endIndex 时
        if (startIndex >= endIndex) {
          return;
        }
        // 得到基准元素位置
        const pivotIndex = partition(arr, startIndex, endIndex);
        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
      }

      /*
       * 分治（单边循环法）
       * @param arr 待交换的数组
       * @param startIndex 起始下标
       * @param endIndex 结束下标
       */
      function partition(arr, startIndex, endIndex) {
        // 取第1个位置(也可以选择随机位置)的元素作为基准元素
        const pivot = arr[startIndex];
        let mark = startIndex;

        for (let i = startIndex + 1; i <= endIndex; i++) {
          if (arr[i] < pivot) {
            mark++;
            const temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
          }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
      }

      const arr = [10, 6, 3, 4, 8, 1, 2];
      quickSort(arr, 0, arr.length - 1);
      console.log(arr);
    </script>
  </body>
</html>
